//
// Created by Administrator on 2024/4/25.
//

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 100; //25
    n = 1000; // 168
    n = 10000; //1229
    n = 100000; //9592
    n = 1000000; //78498 循环921501次
    int count=0;
    bool isP[n + 1] = {0};
    for (int i = 2; i <= n; ++i)
        isP[i] = 1;
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
    {
        if (isP[i])
            primes.push_back(i);
        for (int j = 0; j <= n && primes[j] * i <= n; ++j)
        {
            isP[primes[j] * i] = 0;
            ++count;
            if (i % primes[j] == 0)
                break;
        }
    }
    cout<<count<<endl;
    cout << primes.size();
    return 0;
}